﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Middle_1020_NumEnclaves
{
    class MainProject
    {
        static void Main(string[] args)
        {
            int[][] grid = new int[][]
            {
                new int[]{0,1,1,0 },
                new int[]{0,0,1,0 },
                new int[]{0,0,1,0 },
                new int[]{0,0,0,0 },
            };
            int s = NumEnclaves(grid);
            Console.WriteLine(s);

            Console.ReadKey();
        }
        public static int NumEnclaves(int[][] grid)
        {
            //BFS
            HashSet<int> hash = new HashSet<int>();
            Queue<int> que = new Queue<int>();
            int res = 0;
            int codeIndex;
            for (int i = 0; i < grid.Length; i++)
            {
                for (int j = 0; j < grid[i].Length; j++)
                {
                    codeIndex = i * 1000 + j;
                    if (hash.Contains(codeIndex)) continue;
                    if (grid[i][j] == 1)
                    {
                        que.Enqueue(i * 1000 + j);
                        hash.Add(i * 1000 + j);
                        res += HandleFourSide(grid, que, hash);
                    }
                }
            }
            return res;
        }

        private static int HandleFourSide(int[][] grid, Queue<int> que, HashSet<int> hash)
        {
            int count = 1;

            bool isBorder = false;

            while (que.Count > 0)
            {
                int size = que.Count;
                for (int k = 0; k < size; k++)
                {
                    int code = que.Dequeue();
                    int x = code / 1000;
                    int y = code % 1000;
                    //上左下右
                    if (x - 1 < 0 || y - 1 < 0 || x + 1 >= grid.Length || y + 1 >= grid[x].Length) isBorder = true;
                    if (x - 1 >= 0)
                    {
                        if (grid[x - 1][y] == 1)
                        {
                            if (hash.Add((x - 1) * 1000 + y))
                            {
                                que.Enqueue((x - 1) * 1000 + y);
                                count++;
                            }
                      
                        }
                    }
                    if (y - 1 >= 0)
                    {
                        if (grid[x][y - 1] == 1)
                        {
                            if (hash.Add((x) * 1000 + y - 1))
                            {
                                que.Enqueue((x) * 1000 + y - 1);
                                count++;
                            }
                        }
                    }
                    if (x + 1 < grid.Length)
                    {
                        if (grid[x + 1][y] == 1)
                        {
                            if (hash.Add((x + 1) * 1000 + y))
                            {
                                que.Enqueue((x + 1) * 1000 + y);
                                count++;
                            }
                        }
                    }
                    if (y + 1 < grid[x].Length)
                    {
                        if (grid[x][y + 1] == 1)
                        {
                            if (hash.Add((x) * 1000 + y + 1))
                            {
                                que.Enqueue((x) * 1000 + y + 1);
                                count++;
                            }
                        }
                    }
                }
            }
            return isBorder ? 0 : count;
        }
    }
}
